COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00006 ENDMK
C⊗;
.device xgp
.font 1 "basl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "basi30" <<var>>
.font 4 "basb30" <<bold>>
.TURN ON "←%";
.NOFILL
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY





←CS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1974
←MIDTERM EXAM
%1←Open Books and Notes





.FILL
	Write  LISP  functions  as  follows  using  the  M-expression
notation used in class:


1.	%3get%2[%3y,p%2]%1, where %3y%1 is an S-expression and %3p%1
is a list of A's and D's, is the subexpression of %3y%1 obtained from %3y%1
by taking %4car%1 and %4cdr%1 successively according to the elements of %3p%1.
Thus

	%3get%2 [(A ((B) C) (B)), (D A A)] = (B).%1


2.	%3point%2 [%3x,y%2] is a list of A'S and D's such that
%3get%2 [%3y,point%2 [%3x,y%2]] is the left-most occurrence of the
S-expression %3x%1 in the S-expression %3y%1. Thus

	%3point%2 [(B), (A ((B) C) (B))] = (D A A).%1


3.	%3allpoint%2 [%3x,y%2]%1 is a list of all lists %3p%1 of A's
and D's such that %3get%2 [%3y,p%2] = %3x%1.  Thus

	%3allpoint%2 [(B), (A ((B) C) (B))] = ((D A A) (D D A)).%1


4.	Let a matrix be represented by a list of its rows and each row
by a list of its elements.  %3transpose u%1 is the transpose of the
matrix u, e.g.

	%3transpose %2((A B C) (D E F) (G H I)) = ((A D G) (B E H) (C F I)).%1


5.	Let a set be represented by a list %3u%1 of all its elements.
%3power u%1 is a list of %4all%1 the subsets of %3u%1.  Thus

	%3power %2(A B C) = (NIL (A) (B) (C) (A B) (A C) (B C) (A B C)).%1

I don't especially care about the order of the elements of %3power u%1.